package problems.daily.y2022m7;

import java.util.Arrays;

/**
 * <li style="color: red;">Prob</li>
 * 952. 按公因数计算最大组件大小
 * <li style="color: green;">Desc</li>
 * 给定一个由不同正整数的组成的非空数组 nums ，考虑下面的图：
 *      有 nums.length 个节点，按从 nums[0] 到 nums[nums.length - 1] 标记；
 *      只有当 nums[i] 和 nums[j] 共用一个大于 1 的公因数时，nums[i] 和 nums[j]之间才有一条边。
 * 返回 图中最大连通组件的大小 。
 *
 * <li style="color: green;">Input</li>
 * 1 <= nums.length <= 2 * 104
 * 1 <= nums[i] <= 105
 * nums 中所有值都 不同
 * <li style="color: green;">Output</li>
 *
 * <li style="color: blue;">Link</li>
 * https://leetcode.cn/problems/largest-component-size-by-common-factor/
 * @author habitplus
 * @since 2022/7/30 9:30
 */
public class D20220730_952 {
    // 并查集
    public int largestComponentSize(int[] nums) {
        int m = Arrays.stream(nums).max().getAsInt();
        UnionFind uf = new UnionFind(m + 1);
        for (int num : nums) {
            for (int i = 2; i * i <= num; i++) {
                if (num % i == 0) {
                    uf.union(num, i);
                    uf.union(num, num / i);
                }
            }
        }
        int[] counts = new int[m + 1];
        int ans = 0;
        for (int num : nums) {
            int root = uf.find(num);
            counts[root]++;
            ans = Math.max(ans, counts[root]);
        }
        return ans;
    }

    static class UnionFind {
        // 每个集合的根节点的下标
        int[] parent;
        int[] rank;

        public UnionFind(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
            rank = new int[n];
        }

        public void union(int x, int y) {
            int rx = find(x);
            int ry = find(y);
            // 两个的根节点的下标不一样，就要合并成一个
            // 小的融合到大的集合里面
            if (rx != ry) {
                if (rank[rx] > rank[ry]) {
                    parent[ry] = rx;
                } else if (rank[rx] < rank[ry]) {
                    parent[rx] = ry;
                } else {
                    parent[ry] = rx;
                    rank[rx]++;
                }
            }
        }

        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
    }
}
